package com.aurora.leetcode.answer;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;

/**
 * @author : Aurora
 * @date : 2024/5/14 09:28
 * @description
 * <p>454.四数相加</p>
 * <p>给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：</p>
 * <p></>0 <= i, j, k, l < n</p>
 * <p></>nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0</p>
 * <p>[example1]</p>
 *
 * <p>输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]</p>
 * <p>输出：2</p>
 * <p>解释：</p>
 * <p>两个元组如下：</p>
 * <p>1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0</p>
 * <p>2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0</p>
 */
public class FourSumCount_454 {

    //方法一：暴力遍历  超时
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int n1=0,n2=0,n3=0,n4=0;
        int sum = 0;
        for(int i=0; i<nums1.length; ++i){
            n1 = nums1[i];
            for(int j=0; j<nums2.length; ++j){
                n2 = nums2[j];
                for(int k=0; k<nums3.length; ++k){
                    n3 = nums3[k];
                    for(int l=0; l<nums4.length; ++l){
                        n4 = nums4[l];
                        if(n1 + n2 + n3 + n4 == 0){
                            sum ++;
                        }
                    }
                }
            }
        }
        return sum;
    }

    //方法二：分组+哈希表
    public int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4){
        Map<Integer, Integer> calDoubleNumMap = new HashMap<>();
        int calDoubleNum = 0;
        //先计算两个数组之和，将其放入map<和, 和出现次数>
        for(int i=0; i<nums1.length; ++i){
            for(int j=0; j<nums2.length; ++j){
                calDoubleNum = nums1[i] + nums2[j];
                Integer count = calDoubleNumMap.get(calDoubleNum);
                if(count == null){
                    calDoubleNumMap.put(calDoubleNum, 1);
                }else{
                    calDoubleNumMap.put(calDoubleNum, count+1);
                }
            }
        }
        int result = 0;
        for(int i=0; i<nums3.length; ++i){
            for(int j=0; j<nums4.length; ++j){
                calDoubleNum = nums3[i] + nums4[j];
                Integer integer = calDoubleNumMap.get(calDoubleNum * -1);
                if(integer != null){
                    result += integer;
                }
            }
        }
        return result;
    }


    /**
     * 方法二：写法优化
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount2_impr(int[] nums1, int[] nums2, int[] nums3, int[] nums4){
        Map<Integer, Integer> map = new HashMap<>();
        int calDoubleNum = 0;
        //先计算两个数组之和，将其放入map<和, 和出现次数>
        for(int a : nums1){
            for(int b: nums2){
                map.put(a+b,map.getOrDefault(a+b,0)+1);
            }
        }
        int result = 0;
        for(int a:nums3){
            for(int b:nums4){
                if(map.containsKey(-a-b)){
                    result += map.get(-a-b);
                }
            }
        }
        return result;
    }

    /**
     * 方法二：尝试使用并行流优化执行速度
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount2_impr2(int[] nums1, int[] nums2, int[] nums3, int[] nums4){
        Map<Integer, Integer> map = new ConcurrentHashMap<>();

        IntStream.range(0, nums1.length).parallel().forEach(i -> {
            IntStream.range(0, nums2.length).parallel().forEach(j -> {
                int sum = nums1[i] + nums2[j];
                map.merge(sum, 1, Integer::sum);
            });
        });

        AtomicInteger result = new AtomicInteger(0);

        IntStream.range(0, nums3.length).parallel().forEach(k -> {
            IntStream.range(0, nums4.length).parallel().forEach(l -> {
                int sum = -(nums3[k] + nums4[l]);
                if (map.containsKey(sum)) {
                    result.addAndGet(map.get(sum));
                }
            });
        });

        return result.get();
    }


    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2};
        int[] nums2 = new int[]{-2,-1};
        int[] nums3 = new int[]{-1,2};
        int[] nums4 = new int[]{0,2};
        FourSumCount_454 obj = new FourSumCount_454();
//        System.out.println(obj.fourSumCount(nums1, nums2, nums3, nums4));
//        System.out.println(obj.fourSumCount2(nums1, nums2, nums3, nums4));
        System.out.println(obj.fourSumCount2_impr2(nums1, nums2, nums3, nums4));
    }
}
